class CQueue {
public:
    CQueue() {

    }

    void appendTail(int value) {
        q.push(value);
    }

    int deleteHead() {
        if (q.empty()) return -1;
        int front = q.front();
        q.pop();
        return front;
    }
private:
    queue<int> q;
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

 /**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
  */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (!root) return {};
        queue<TreeNode*> q;
        q.push(root);
        int level = 1;
        while (q.size())
        {
            int sz = q.size();
            vector<int> tmp;
            for (int i = 0; i < sz; i++)
            {
                TreeNode* front = q.front();
                q.pop();
                tmp.push_back(front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            if (level % 2 == 0) reverse(tmp.begin(), tmp.end());
            ret.push_back(tmp);
            level++;
        }
        return ret;
    }
};